Природни бројеви се могу трансформисати коришћењем следеће две операције:

• множење било којим другим природним бројем (може се применити увек)

• кореновање (може се применити само ако број потпун квадрат тј. ако је његов корен поново природан број).

Напиши програм који за дати број \(n\) одређује најмањи број који се може добити применом ове две операције.

Улаз

Са стандардног улаза се учитава природан број \(n\) (\(1 \leq n \leq 10^{12}\)).

Излаз

На стандардни излаз исписати тражени најмањи број.

Пример 1

Улаз

20

Излаз

10

Објашњење

Број 20 се може помножити бројем 5, а затим се може кореновати и тако добити број 10. Ниједан број мањи од 10 није могуће добити.

Пример 2

Улаз

540

Излаз

30

Објашњење

Број 540 се може помножити бројем 1500, а затим се може два пута кореновати и тако добити број 30. Ниједан број мањи од 30 није могуће добити.